package problems.practice;

/**
 * 424. 替换后的最长重复字符
 * https://leetcode.cn/problems/longest-repeating-character-replacement/
 *
 * @author habitplus
 * @since 2022/8/13 18:08
 */
public class T424 {
    // 双指针 + map计数
    public int characterReplacement(String s, int k) {
        if (s == null || s.length() < 1 || k < 0) return 0;

        char[] chs = s.toCharArray();
        int[] cntMap = new int[26];
        int n = chs.length;
        int l = 0, r = 0;
        int maxLen = 0;
        int idx;

        while (r < n) {
            idx = chs[r] - 'A';
            cntMap[idx]++;
            maxLen = Math.max(cntMap[idx], maxLen);
            if (r - l - maxLen + 1 > k) {
                cntMap[chs[l] - 'A']--;
                l++;
            }
            r++;
        }

        return r - l;
    }
}
